/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	Question057
 * 模块说明：
 * 修改历史：
 * 2025/1/21 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals
 * 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
 * <p>
 * <p>
 * <p>
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。返回插入之后的
 * intervals。
 * <p>
 * 示例1： 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * <p>
 * 输出：[[1,5],[6,9]]
 * <p>
 * 示例2： 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * <p>
 * 输出：[[1,2],[3,10],[12,16]]
 * <p>
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 */
public class Question057 {


  public static void main(String[] args) {
    int[][] intervals = { { 1, 3 }, { 6, 9 } };
    int[][] insert = insert(intervals, new int[] { 2, 5 });
    System.out.println(JSON.toJSONString(insert));
  }

  public static int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> ans = new ArrayList<>();

    for (int[] interval : intervals) {

      if (newInterval == null || interval[1] < newInterval[0]) {
        // 前面单独的添加进来，或者已经合并完了，把后面的添加进来
        ans.add(interval);
      } else if (newInterval[1] < interval[0]) {
        ans.add(newInterval); // 后面单独的区间o
        ans.add(interval);
        newInterval = null;
      } else { // 合并区间
        newInterval[0] = Math.min(newInterval[0], interval[0]);
        newInterval[1] = Math.max(newInterval[1], interval[1]);
      }
    }
    if (newInterval != null) {
      ans.add(newInterval);
    }
    return ans.toArray(new int[ans.size()][]);
  }

}
